package datastructure.sort;

import datastructure.utils.Common;

public class Insert {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        int length = arr.length;

        for (int i = 0; i < length; i++) {

//            直接将arr[i]插入到合适的位置
            E temp = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    /**
     * 对数组 arr 从区间 [start, end] 进行插入排序
     * @param arr 排序数组
     * @param start 起始位置
     * @param end 终止位置
     * @param <E> 实现 Comparable 的泛型
     */
    public static <E extends Comparable<E>> void sort(E[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        for (int i = start; i <= end; i++) {

//            直接将arr[i]插入到合适的位置
            E temp = arr[i];
            int j;
            for (j = i; j - 1 >= start && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

//    未优化
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        int length = arr.length;

        for (int i = 0; i < length; i++) {

            for (int j = i; j - 1 >= 0; j--) {
                if (arr[j - 1].compareTo(arr[j]) > 0)
                    Common.swapArray(arr, j-1, j);
                else
                    break;
            }
        }
    }
}
